package org.test.analysis;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import org.junit.Test;
import org.test.analysis.Num.direction;

/**
 * 生成全排列
 * 
 * @author game
 * 
 */
public class FullArray {

	@Test
	public void testgetAllarrange() {
		System.out.println((new Arrangementnum(4)).getAllArange());
	}

	// @Test
	// public void testswap() {
	// Arrangementnum arrangementnum = new Arrangementnum(10);
	// arrangementnum.swapmaxAndchangeBigerDir(6);
	// }
}

/**
 * 对排列的记录类，
 * 
 * @author game
 * 
 */
class Arrangementnum {

	/**
	 * 初始数组
	 */
	private Num[] nums;

	/**
	 * 是否有移动元素
	 */
	private boolean hasMaxMoveNum;

	/**
	 * 比移动元素大的num
	 */
	private int[] bigerIndex;

	/**
	 * 全排列存入　
	 */
	private List<String> arrangeList = new ArrayList<String>();

	/**
	 * 初始化
	 * 
	 * @param n
	 */
	public Arrangementnum(int n) {
		nums = new Num[n];
		for (int i = 0; i < n; i++) {
			nums[i] = new Num(i);
		}
		this.setHasMaxMoveNum(true);
	}

	/**
	 * 把移动元素和它旁边的交换,后设置大于k的元素方向
	 * @param num
	 */
	public void swapmaxAndchangeBigerDir(int index) {
		Num swaptmp;
		// 换
		if (nums[index].getDir() == Num.direction.left) {// 向左换
			swaptmp = nums[index];
			nums[index] = nums[index - 1];
			nums[index - 1] = swaptmp;
		} else {// 向右换
			swaptmp = nums[index];
			nums[index] = nums[index + 1];
			nums[index + 1] = swaptmp;
		}
		// 设置方向
		if (bigerIndex != null) {
			for (int j = 0; (j < bigerIndex.length) && (bigerIndex[j] != -1); j++) {
				nums[bigerIndex[j]].changedir();
			}

		}
	}

	// 得到所有全排列
	public List<String> getAllArange() {
		int maxin;
		List<String> arrangeList = new ArrayList<String>();

		// 第一个数放到排列中
		StringBuffer arrangeString = new StringBuffer();
		for (int i = 0; i < nums.length; i++) {
			arrangeString.append(nums[i].getValue() + ",");
		}
		arrangeList.add(arrangeString.toString());
		while (true) {
			maxin = this.getMaxInArray(); // 取最大
			// 是否还有移动元素
			if (this.isHasMaxMoveNum()) {
				this.swapmaxAndchangeBigerDir(maxin);// 交换

				// 放到排列中
				arrangeString = new StringBuffer();
				arrangeString = new StringBuffer();
				for (int i = 0; i < nums.length; i++) {
					arrangeString.append(nums[i].getValue() + ",");
				}
				arrangeList.add(arrangeString.toString());
			} else {
				return arrangeList;
			}
		}
	}

	/**
	 * 在num[]里面找出最大的移动元素
	 * 
	 * @param nums
	 */
	public int getMaxInArray() {
		int n = nums.length;
		int tmp[] = new int[n + 1]; // 存是为移动元素的序号
		for (int i = 0; i < tmp.length; i++) {// 始化为　－１
			tmp[i] = -1;
		}
		int index = 0;

		// 循环，查找移动元素
		for (int i = 0; i < nums.length; i++) {
			if (nums[i].getDir() == direction.left) {// 往左
				if ((i - 1) >= 0) {
					if (nums[i - 1].getValue().compareTo(nums[i].getValue()) < 0) { // 后面的比较大
						tmp[index++] = i; // 第i个元素为移动元素
					}
				}
			} else { // 往右
				if ((i + 1) < n) {
					if (nums[i + 1].getValue().compareTo(nums[i].getValue()) < 0) { // 后面的比较小
						tmp[index++] = i; // 第i个元素为移动元素
					}
				}
			}
		}// end for

		int maxindex = tmp[0];// 最大移动元素的index
		if (tmp[0] == -1) {// 没有移动元素，说明要OVER了,max这时为-1
			this.setHasMaxMoveNum(false);// 把boolean附false
		} else {
			for (int i = 1; (i < tmp.length) && (tmp[i] != -1); i++) {
				if (nums[tmp[i]].getValue()
						.compareTo(nums[maxindex].getValue()) > 0) { // 比max大,则把max新附值
					maxindex = tmp[i];
				}
			}

			// 找出比最大移动元素还要大的元素，加进去　
			bigerIndex = new int[n];
			for (int i = 0; i < bigerIndex.length; i++) {
				bigerIndex[i] = -1;
			}
			for (int i = 0, j = 0; i < nums.length; i++) {
				if (nums[i].getValue().compareTo(nums[maxindex].getValue()) > 0) {
					bigerIndex[j++] = i;
				}
			}
		}
		return maxindex;
	}

	/**
	 * @return the nums
	 */
	public Num[] getNums() {
		return nums;
	}

	/**
	 * @param nums
	 *            the nums to set
	 */
	public void setNums(Num[] nums) {
		this.nums = nums;
	}

	/**
	 * @return the hasMaxMoveNum
	 */
	public boolean isHasMaxMoveNum() {
		return hasMaxMoveNum;
	}

	/**
	 * @param hasMaxMoveNum
	 *            the hasMaxMoveNum to set
	 */
	public void setHasMaxMoveNum(boolean hasMaxMoveNum) {
		this.hasMaxMoveNum = hasMaxMoveNum;
	}

	/**
	 * @return the bigerIndex
	 */
	public int[] getBigerIndex() {
		return bigerIndex;
	}

	/**
	 * @param bigerIndex
	 *            the bigerIndex to set
	 */
	public void setBigerIndex(int[] bigerIndex) {
		this.bigerIndex = bigerIndex;
	}

	/**
	 * @return the arrangeList
	 */
	public List<String> getArrangeList() {
		return arrangeList;
	}

	/**
	 * @param arrangeList
	 *            the arrangeList to set
	 */
	public void setArrangeList(List<String> arrangeList) {
		this.arrangeList = arrangeList;
	}
}

/**
 * 自定义number类，有方向
 * 
 * @author game
 * 
 */
class Num {
	public enum direction {
		left, right
	};
	/**
	 * 方向
	 */
	private direction dir;
	/**
	 * 值
	 */
	private Integer value;

	public Num(Integer integer) {
		this.value = integer;
		this.dir = direction.left; // 全部初始化为往左
	}

	/**
	 * 改方向
	 */
	public void changedir() {
		if (dir == direction.left) {
			dir = direction.right;
		} else {
			dir = direction.left;
		}
	}

	public direction getDir() {
		return dir;
	}

	public void setDir(direction dir) {
		this.dir = dir;
	}

	public Integer getValue() {
		return value;
	}

	public void setValue(Integer value) {
		this.value = value;
	}
	/*
	 * (non-Javadoc)
	 * 
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		// TODO Auto-generated method stub

		// return "value为：" + value + ",序号为" + serial + ",方向为" + dir;
		return value + "_" + dir;
	}

}
